package recfun

object Main {
  def main(args: Array[String]) {
    println("Pascal's Triangle")
    for (row <- 0 to 10) {
      for (col <- 0 to row)
        print(pascal(col, row) + " ")
      println()
    }
  }

  /**
   * Exercise 1
   */
  def pascal(c: Int, r: Int): Int = {
    if (c == 0 || r == 0 || c == r)
      1
    else
      pascal(c-1, r-1) + pascal(c, r-1)
  }

  /**
   * Exercise 2
   */
  def balance(chars: List[Char]): Boolean = {
    def compare(flag: Int, seq: List[Char]): Boolean = {
      if (flag < 0)
        false
      else if (seq.isEmpty)
        flag == 0
      else if (seq.head == '(')
        compare(flag + 1, seq.tail)
      else if (seq.head == ')')
        compare(flag - 1, seq.tail)
      else
        compare(flag, seq.tail)
    }

    compare(0, chars)
  }

  /**
   * Exercise 3
   */
  def countChange(money: Int, coins: List[Int]): Int = {
    val sortedCoins = coins.sorted
    if (money == 0)
      1
    else if (sortedCoins.isEmpty || money < sortedCoins.head)
      0
    else
      countChange(money, sortedCoins.tail) + countChange(money - sortedCoins.head, sortedCoins)
  }
}
